#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param grid int整型vector<vector<>>
     * @return int整型
     */

    int n, m;
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    bool check[1001][1001] = {false};
    queue<pair<int, int>> q;
    int rotApple(vector<vector<int>> &grid)
    {
        n = grid.size(), m = grid[0].size();
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (grid[i][j] == 2)
                {
                    check[i][j]=true;
                    q.push({i, j});
                }
            }
        }
        int ret = 0; // 记录bfs向外扩展的层数
        while (q.size())
        {
            int sz = q.size();
            while (sz--)
            {
                auto [a, b] = q.front();
                q.pop();
                for(int k=0;k<4;k++)
                {
                    int x=dx[k]+a;
                    int y=dy[k]+b;
                    if(x>=0&&x<n&&y>=0&&y<m&&grid[x][y]==1&&check[x][y]==false)
                    {   
                        check[x][y]=true;
                        q.push({x,y});
                    }
                }
            }
            ret++;

        }
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(grid[i][j]==1&&check[i][j]==false) return -1;
            }
        }
        return ret-1;
    }
};